/*
 * string.cpp
 *
 *  Created on: Jul 13, 2012
 *      Author: xkq
 */

#include <string>
#include <cstring>
#include <iostream>
#include <climits>
#include <ext/hash_map>
#include <sstream>
using namespace std;

void remove_spaces_from_a_string(char *str){
	if(!*str) return;
	char *pt=str;
	while(*str++){
		if(*str==' ') continue;
		*pt=*str;
	}
	*pt='\0';
}

/* 7/26/2012 MSFT Telephone interview, remove duplicate spaces from input string*/
char* remove_spaces(char *str){
	if(!*str) return NULL;

	char *fast = str;
	char *slow = str;
	bool isSpace = false;
	while(*fast !='\0'){
		if(*fast==' '&&!isSpace){
			isSpace = true;
		}else if(*fast == ' '&& isSpace){
			fast++;
			continue;
		}else{
			isSpace = false;
		}
		*slow++=*fast++;
	}
	*slow = '\0';
	return str;
}


int count_number_of_words_in_a_string(char *str){
	if(!*str) return 0;
	bool inWord = false;
	int count=0;
	while(*str){
		if(!inWord && isalpha(*str)){
			count++;
			inWord=true;
		}
		else if(inWord && *str==' '){
			inWord=false;
		}
		str++;
	}
	return count;
}

///////////////////////////////////////////////////////////////////////
// Reverse the word order in a sentence, but maintain the character
// order inside a word
// Input: pData - the sentence to be reversed
///////////////////////////////////////////////////////////////////////
char* reverse_words_in_sentence(char *s){
	if(!*s) return NULL;

	char *p2=s;
	char *p1=s;
	while(*p2!='\0')
		p2++;
	p2--;
	while(p1>=p2){
		char tmp = *p2;
		*p2=*p1;
		*p1=tmp;
	}

	p1=s;
	p2=s;
	while(*p2!='\0'){
		if(*p2!=' ')
			p2++;
		else if(*p2==' '){
			char *tmp2=p2;
			p2--;
			while(p1>=p2){
				char tmp = *p2;
				*p2=*p1;
				*p1=tmp;
			}
			p2=tmp2;
			while(*p2!=' ')
				p2++;
			p1=p2;
		}
	}
	return s;
}

///////////////////////////////////////////////////////////////////////
// Convert a string into an integer
///////////////////////////////////////////////////////////////////////
bool str_to_int(const char *str, long long &num){
	num = 0;

	if(str!=NULL){
		const char *digit=str;
		bool minus= false;
		if(*str == '-'){
			minus = true;
			digit++;
		}
		else digit++;
		if(*digit=='\0')
			return false;
		while(*digit!='\0'){
			if('0'<=*digit&&*digit<='9'){
			num=num*10+*digit-'0';
			if(num>INT_MAX)
			{	num=0;
				return false;
			}
			}else{
				num=0;
				return false;
			}
			digit++;
		}
		if(minus)
			num=0-num;
	}else{
		return false;
	}
	return true;
}

///////////////////////////////////////////////////////////////////////
// Delete all characters in pStrDelete from pStrSource
///////////////////////////////////////////////////////////////////////

void delete_chars(char *str, const char *del){
	if(str==NULL || del == NULL)
		return;

/*	__gnu_cxx::hash<char*> m;*/
	int tableSize = 256;
	int hashTable[tableSize];
	for(int i=0; i<tableSize; i++)
		hashTable[i] = 0;
	const char *tmp = del;
	while(*tmp!='\0'){
		hashTable[(int)*tmp] = 1;
		tmp++;
	}

	char *slow = str;
	char *fast = str;

	while(*fast!='\0'){
		if(1!=hashTable[(int)*fast])
		{
			*slow=*fast;
			++slow;
		}
		++fast;
	}
	*slow='\0';
}

/*longest palindrome substring*/
string expand_around_center(string s, int l, int r){
	int n = s.length();
	while(l>=0 && r<=n-1 && s[l]==s[r])
	{
		l--;
		r++;
	}
	return s.substr(l+1, r-l+1);
}

string longestPalindromeSimple(string s){
	int n = s.length();
	if (n==0) return "";
	string longest=s.substr(0,1);
	for(int i=0; i<n-1;i++){
		string p1=expand_around_center(s, i, i);
		if(p1.length()>longest.length())
			longest = p1;

		string p2=expand_around_center(s, i, i+1);
		if(p2.length()>longest.length())
			longest = p2;
	}
	return longest;
}

///////////////////////////////////////////////////////////////////////
// Find the first char which appears only once in a string
// Input: pString - the string
// Output: the first not repeating char if the string has, otherwise 0
///////////////////////////////////////////////////////////////////////
char first_not_repeating_char(char *str){
	if(str == NULL) return 0;

	const int tableSize = 256;
	unsigned int hashTable[tableSize];

	for(int i=0; i<tableSize; i++)
		hashTable[i]=0;

	char *p=str;

	while(*str!='\0'){
		hashTable[(int)*p]++;
		p++;
	}

	p=str;

	while(*p!='\0'){
		if(hashTable[(int)*p]==1)
			return *p;
		p++;
	}

	return 0;
}

/*Write C code to implement the strstr (Search for a substring) function. Do not use any system library such as strlen.
Improvement is N-M+1 by having a char* to record how many chars we have until reach to the end of str. */
char * find_subtring(const char *str, const char *target){
	if(!*target) return (char *)str;
	char *p1 = (char*)str;

	while(*p1){
		char *p1Begin = p1, *p2 = (char *)target;
		while(*p1==*p2&&*p1&&*p2){
			p1++;
			p2++;
		}
		if(!*p2)
			return p1Begin;
		p1=p1Begin+1;
	}
	return NULL;
}

/*Replace all occurrence of the given pattern to æ…©ï¿½
For example, given that the pattern=æ”�bcï¿½ replace æ�³bcdeffdfegabcabcï¿½with æ�¦deffdfegXï¿½
Note that multiple occurrences of abcæŠ¯ that are contiguous will be replaced with only one æ…©ï¿½*/

bool isMatched(char *str, char *pattern){
	while(*pattern != '\0'){
		str++;
		pattern++;
		if(*str!=*pattern)
			return false;
	}
	return true;
}

void string_replace(char *str, char *pattern){
	if(!*str||!*pattern) return;
	char *fast = str, *slow = str;
	int patternLen = strlen(pattern);
	while(*fast != '\0'){
		if(*fast == *pattern){
			bool matched = isMatched(fast, pattern);
			if(matched){
				fast += patternLen;
				*slow++ = 'X';
			}else
				*slow++=*fast++;
		}else
			*slow++=*fast++;
	}
	*slow = '\0';
}

/*Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without
 * repeating letters for â€œabcabcbbâ€� is â€œabcâ€�, which the length is 3. For â€œbbbbbâ€� the longest substring is â€œbâ€�, with the length of 1.*/

int longest_substring_without_repeating_char(string str){
	int len = str.length();
	int i=0, j=0, maxLen=0;
	bool exist[256] = {false};
	while(j<len){
		if(exist[str[j]]){
			maxLen = max(j-i, maxLen);
			while(str[i]!=str[j]){
				i++;
				exist[i]==false;
			}
			i++;
		}else{
			exist[str[j]] = true;
		}
		j++;
	}
	maxLen = max(len-i, maxLen);
	return maxLen;
}

/*How to replace the space in the string with "ABC" without using extra memory.*/
char* space_replacement(char *str, const char *pattern){
	if(str==NULL||pattern==NULL) return NULL;

	int spaceNum = 0;
	char *p = str;
	while(*p!='\0'){
		if(*p==' ')
			spaceNum++;
		p++;
	}
	int patternLen = 0;
	char *pp = (char *)pattern;
	while(*pp!='\0'){
		patternLen++;
		pp++;
	}
	pp--;
	char *tmp=p;
	p+=(patternLen-1)*spaceNum;
	while(p!=str){
		if(*tmp!=' ')
			*p=*tmp;
		else{
			char *copy = pp;
			while(copy!=pattern){
				*p=*copy;
				p--;
				copy--;
			}
			*p=*copy;
		}
		p--;
		tmp--;
	}
	*p=*tmp;
	return str;
}

/*int main(){
	char s1[] = "ab c";
	const char s2[] = "ABC";
	string input = "";
	getline(cin, input);
	cout << input << endl;
	cout << space_replacement(s1, s2) << endl;
	return 0;
}*/
